import java.math.BigInteger;
import java.util.Date;
import java.util.LinkedList;
import java.util.Random;

import javax.naming.TimeLimitExceededException;

public class PollardRho {
	Kattio io = new Kattio(System.in,System.out);
	private final static BigInteger ZERO = BigInteger.ZERO;
	private final static BigInteger ONE = BigInteger.ONE;
	private final static BigInteger TWO = new BigInteger("2");
	private final static Random random = new Random(System.currentTimeMillis());
	private static Date endTime = null;

	public static void main(String[] args){
		Kattio io =  new Kattio(System.in, System.out);
		//			//This is for test
		//			FastBigInteger bi = new FastBigInteger(100,random);
		//			bi = new FastBigInteger("154260010606791054558985040339");
		//			System.out.println("--------------NUMBER TO FACTORIZE--------------\n"+bi+"\n--------------PRIME FACTORIZATION--------------");
		//			printfactors(bi);
		//			io.flush();

		//This is for sending to kattis
		while(io.hasMoreTokens()){
			try{
				endTime = new Date(System.currentTimeMillis()+1000000);
				BigInteger n = new BigInteger(io.getWord());
				if(n.bitLength()>100){
					io.println("fail");
				} else {
					LinkedList<String> ll = new LinkedList<String>();
					long time = System.currentTimeMillis();
					getfactors(n,ll, true);
					for(String s : ll){
						io.println(s);
					}
					System.out.println("-------------------");
					System.out.println(time - System.currentTimeMillis());
				}
				io.println();
			} catch(TimeLimitExceededException e){
				io.println("fail");
				io.println();
			}
			io.flush();
		}
		io.flush();
	}

	
	public static void printfactors(BigInteger n) throws TimeLimitExceededException{
		Kattio io = new Kattio(System.in, System.out);
		LinkedList<String> ll = new LinkedList<String>();
		getfactors(n, ll, true);
		for(String s : ll){
			io.println(s);
		}
		io.flush();
	}

	public static void getfactors(BigInteger n, LinkedList<String> ll, boolean firstInput) throws TimeLimitExceededException{
		if (n.compareTo(ONE) == 0){
			return;
		}

		if(n.isProbablePrime(20)){
			ll.add(n.toString());
			return; 
		}
		BigInteger f1 = pollardRho(n);
		BigInteger f2 = n.divide(f1);
		getfactors(f1,ll, false);
		getfactors(f2,ll, false);
	}

	public static BigInteger pollardRho(BigInteger n) throws TimeLimitExceededException{

		if (n.mod(TWO).compareTo(ZERO) == 0){
			return TWO;
		}
		BigInteger c = new BigInteger(n.bitLength(),random);
		BigInteger x = new BigInteger(n.bitLength(),random).mod(n);
		BigInteger y = x;
		BigInteger d = ONE;
		BigInteger ret;
		int i = 0;

		while(true){
			i++;
			if(new Date().after(endTime)){
				throw new TimeLimitExceededException();
			}
			x = f(c,x,n);
			y = f(c,f(c,y,n),n);
			ret = x.subtract(y);
			d = ret.multiply(d).mod(n);
			if(i % 100 == 0){
				if((ret = ret.gcd(n)).compareTo(ONE)!=0){
					break;
				}
			}
		}
		return ret;
	}
	
	public static BigInteger pollardBrent(BigInteger n) throws TimeLimitExceededException{
		BigInteger x, xt, tmp, bound;
		int k,a,d, x0;
		boolean found;

		// Choose x0
		x0 = 3;
		
		// Helper
		xt = new BigInteger(x0 + "");
		x = new BigInteger(x0 + "");
		d = 0;
		k = 1;
		a = 2;
		bound = n.divide(new BigInteger("2"));
		found = false;
		
		while(new BigInteger(d+"").compareTo(bound) != 0)
		{	
			// Check if k is next 2^(a+1) bit-number
			// Then set new xt.
			if(k >= (int) Math.pow(2, a) && k < Math.pow(2, a+1))
				{ xt = x;	a++; }
			x =  f(ONE,x,n);
			tmp = (x.subtract(xt).abs()).gcd(n);	

			if(tmp.compareTo(new BigInteger("1")) != 0 && tmp.compareTo(n) != 0)
			{
				found = true;
				return tmp;
			}
			k++; d++;
		}
		return null;
	}


	private static BigInteger f(BigInteger c, BigInteger x,BigInteger n){
		return (x.multiply(x)).subtract(c).mod(n);
	}
}